//
// Created by martin on 9/9/21.
//

#include "hashmap.h"
#include <stdio.h>
#include <string.h>


// 申请HashMap存储空间
#define newHashMap() NEW(struct hashmap);
// 默认哈希函数
static int defaultHashCode(HashMap hashMap, let key);
// 默认判断键值是否相等函数
static Boolean defaultEqual(let key1, let key2);
// 默认添加键值对函数
static void defaultPut(HashMap hashMap, let key, let value);
// 默认获取键对应值函数
static let defaultGet(HashMap hashMap, let key);
// 默认删除键
static Boolean defaultRemove(HashMap hashMap, let key);
// 默认判断是否存在指定键值的函数
static Boolean defaultExists(HashMap hashMap, let key);
// 默认清除map的函数
static void defaultClear(HashMap hashMap);
// 重置HashMap
static void rehash(HashMap hashMap, int listSize);
// 默认创建Entry对象的函数
Entry defaultNewEntry0(let key, let value);
// 默认释放Entry对象的函数
void defaultFreeEntry0(Entry *entry);

/**
 * 默认哈希函数, 计算哈希值, 使用ELF Hash算法
 */
int defaultHashCode(HashMap hashMap, let key)
{
    if (!hashMap || !key) return 0;
    char *k = (char *)key;
    unsigned long hash = 0;
    unsigned long g = 0;

    while (*k) {
        hash = (hash << 4) + (*k++);
        g = hash & 0xF0000000L;
        if (g) {
            hash ^= g >> 24;
        }
        hash &= ~g;
    }
    return hash % hashMap->listSize;
}

Boolean defaultEqual(let key1, let key2)
{
    if (!key1 || !key2) return False;
    string s1 = (string)key1;
    string s2 = (string)key2;

    return strcmp(s1, s2) == 0 ? True : False;
}

/**
 * 默认创建Entry对象的函数，把参数key和value当作字符串，Entry对象key和value域分别拷贝一份（深度拷贝）
 */
Entry defaultNewEntry0(let key, let value)
{
    if (!key) return NULL;

    Entry entry = (Entry) malloc(sizeof(struct entry));
    entry->key = strcpy(malloc(strlen(key) + 1), key) ;
    entry->value = strcpy(malloc(strlen(value) + 1), value);
    entry->next = NULL;
    return entry;
}

// 默认释放Entry对象的函数
void defaultFreeEntry0(Entry *entry)
{
    if (!entry) return;
    if (*entry) {
        free((*entry)->key);
        free((*entry)->value);
        free(*entry);
        *entry = NULL;
    }

    entry = NULL;
}

HashMap createHashMap(HashCode hashCode, Equal equal)
{
    HashMap hashMap = newHashMap();
    if (!hashMap) {
        return NULL;
    }

    memset(hashMap, 0, sizeof(struct hashmap));
    hashMap->size = 0;
    hashMap->listSize = HASHMAP_LISTSIZE_INITIAL;
    hashMap->hashCode = (hashCode == NULL? defaultHashCode : hashCode);
    hashMap->equal = (equal == NULL? defaultEqual : equal);
    hashMap->get = defaultGet;
    hashMap->put = defaultPut;
    hashMap->exists = defaultExists;
    hashMap->remove = defaultRemove;
    hashMap->clear = defaultClear;
    hashMap->autoAssign = True;
    hashMap->loadFactor = HASHMAP_LAODFACTOR_INITIAL;
    hashMap->threadHold = (int)((float)hashMap->listSize * hashMap->loadFactor);

    hashMap->newEntry = defaultNewEntry0;
    hashMap->freeEntry = defaultFreeEntry0;

    // 起始分配8个内存空间，溢出时自动扩容
    hashMap->list = newEntryList(hashMap->listSize);
    if (!hashMap->list) {
        free(hashMap);
        return NULL;
    }

    Entry p = hashMap->list;
    int i;
    for (i = 0; i < hashMap->listSize; ++i) {
        p[i].key = NULL;
        p[i].value = NULL;
        p[i].next = NULL;
    }

    return hashMap;
}

/**
 * 根据key获取value值
 */
let defaultGet(HashMap hashMap, let key)
{
    if (!hashMap || !key) return NULL;
    // 根据key求出元素在数组中的位置
    int index = hashMap->hashCode(hashMap, key);
    // 获取冲突链表首节点，即数组元素所在节点
    Entry entry = &hashMap->list[index];

    // 遍历冲突链表，找到key位置
    while (entry != NULL) {
        if (hashMap->equal(entry->key, key)) {
            return entry->value;
        }
        entry = entry->next;
    }

    return NULL;
}

void defaultPut(HashMap hashMap, let key, let value)
{
    if (!hashMap || !key) return;
    // 根据key求出元素在数组中的位置
    int index = hashMap->hashCode(hashMap, key);

    if (hashMap->list[index].key == NULL) {
        // 数组槽位空，直接存储键值对
        hashMap->list[index].key = newString(key);
        hashMap->list[index].value = newString(value);
    }
    else {
        // 数组槽位非空
        // 先遍历链表，查找是否有相同key，如果有就更新value；如果没有，就在数组槽位后插入新节点
        Entry entry = &hashMap->list[index];
        while (entry != NULL) {
            if (hashMap->equal(entry->key, key)) {
                // 已经存在键值，则直接覆盖value
                // TODO 注意：这里value如果是动态内存，就要考虑如何释放的问题
                freeString(entry->value);
                entry->value = newString(value);
                return;
            }
            entry = entry->next;
        }

        // 键值不存在，数组槽位后插入节点
        Entry new_entry = newEntry();
        new_entry->key = newString(key);
        new_entry->value = newString(value);
        new_entry->next = hashMap->list[index].next;
        hashMap->list[index].next = new_entry;

        hashMap->size++;
    }

    if (hashMap->autoAssign && hashMap->size > hashMap->threadHold) {
        rehash(hashMap, hashMap->listSize * 2); /* 扩容一倍 */
    }
}

/**
 * 删除指定key，返回key关联的值
 * @return 返回key关联的值
 * -NULL 如果key映射值为NULL，或key不存在与map中，返回NULL
 */
Boolean defaultRemove(HashMap hashMap, let key)
{
    if (!hashMap || !key) return False;

    int index = hashMap->hashCode(hashMap, key);
    Entry entry = &hashMap->list[index];
    if (entry->key == NULL) {
        // 数组槽位为空，key不可能在map中
        return False;
    }

    let rm_value = NULL;
    Boolean rm_res = False;
    // 要移除的节点是冲突链表首节点,但是不可能直接释放数组元素，想办法把冲突链表后面元素前移
    if (hashMap->equal(entry->key, key)) {
        hashMap->size--;
        if (entry->next != NULL) { // 链表第二个节点非空
            rm_value = entry->value;

            // 将链表第二个节点内容拷贝到首节点
            Entry temp_entry = entry->next;
            freeString(entry->key);
            freeString(entry->value);
            entry->key = temp_entry->key;
            entry->value = temp_entry->value;
            entry->next = temp_entry->next;
            // 释放链表第二个节点
            free(temp_entry);
        }
        else {
            // 链表第二个节点为空
            // 清空首节点内容
            freeString(entry->key);
            freeString(entry->value);
            entry->key = NULL;
            entry->value = NULL;
        }
        rm_res = True;
    }
    else {
        // 要移除的节点不是首节点，先在链表中查找，如果找到就删除对应节点;如果没找到，就直接返回null
        Entry prev_entry = entry;
        entry = entry->next;
        while (entry != NULL) {
            if (hashMap->equal(entry->key, key)) {
                hashMap->size--;
                rm_value = entry->value;

                prev_entry->next = entry->next;
                freeString(entry->key);
                freeString(entry->value);
                free(entry);
                rm_res = True;
                break;
            }
            prev_entry = entry;
            entry = entry->next;
        }
    }

    return rm_res;
}

Boolean defaultExists(HashMap hashMap, let key)
{
    if (!hashMap || !key) return False;

    int index = hashMap->hashCode(hashMap, key);
    Entry entry = &hashMap->list[index];
    Boolean res = False;

    if (entry->key == NULL) {
        return False;
    }

    while (entry != NULL) {
        if (hashMap->equal(entry->key, key)) {
            res = True;
            break;
        }
        entry = entry->next;
    }

    return res;
}

void defaultClear(HashMap hashMap)
{
    if (!hashMap) return;

    int i;
    for (i = 0; i < hashMap->listSize; ++i) {
        // 释放冲突链表(不包含首节点，即数组）
        Entry entry = hashMap->list[i].next;
        while (entry != NULL) {
            Entry next = entry->next;
            freeString(entry->key);
            freeString(entry->value);
            free(entry);
            entry = next;
        }
        hashMap->list[i].next = NULL;
    }

    free(hashMap->list);
    hashMap->list = NULL;
    hashMap->listSize = 0;
    hashMap->size = 0;
}

void rehash(HashMap hashMap, int listSize)
{
    if (!hashMap || listSize < HASHMAP_LISTSIZE_INITIAL) return;
    int i;

    // 所有现有键值对临时存储空间
    int length = hashMap->size;
    Entry temp_all_entrys = newEntryList(length);
    if (!temp_all_entrys) {
        perror("rehash newEntryList error");
        return;
    }

    // 创建迭代器，用于遍历Hashmap
    HashMapIterator iterator = createHashMapIterator(hashMap);
    if (!iterator) {
        perror("rehash createHashMapIterator error");
        return;
    }

    // 通过迭代器，取出所有键值对，并存放到临时存储空间
    for (i = 0; hasNextHashMapIterator(iterator); ++i) {
        // 迭代取出所有键值对
        iterator = nextHashMapIterator(iterator);
        temp_all_entrys[i].key = iterator->entry->key;
        temp_all_entrys[i].value = iterator->entry->value;
        temp_all_entrys[i].next = NULL; /* 无需next域 */
    }
    freeHashMapIterator(&iterator);

    // 清除原有map所有键值对数据
    hashMap->size = 0;
    for (i = 0; i < hashMap->listSize; ++i) {
        Entry entry = &hashMap->list[i];
        // TODO 如果是动态内存，必须考虑空间释放问题
        // 因为旧的map中所有的key/value, 都转移到temp_all_entrys临时空间中，所以此处不用考虑key/value的释放问题
        entry->key = NULL;
        entry->value = NULL;
        // 释放冲突链表空间
        while (entry->next != NULL) {
            Entry temp = entry->next->next;
            free(entry->next);
            entry->next = temp;
        }
    }

    // 更改内存大小
    // 为何只释放冲突链表，而不释放数组？因为会使用realloc重新分配数组空间
    hashMap->listSize = listSize;
    Entry rehash_list = (Entry) realloc(hashMap->list, listSize * sizeof(struct entry));
    if (!rehash_list) {
        perror("rehash realloc error");
        return;
    }

    hashMap->list = rehash_list;
    rehash_list = NULL;

    // 初始化新存储空间所有数据
    for (i = 0; i < hashMap->listSize; ++i) {
        hashMap->list[i].key = NULL;
        hashMap->list[i].value = NULL;
        hashMap->list[i].next = NULL;
    }

    // 将所有键值对重新插入新存储空间
    for (i = 0; i < length; ++i) {
        hashMap->put(hashMap, temp_all_entrys[i].key, temp_all_entrys[i].value);
    }



    free(temp_all_entrys);
}

void freeHashMap(HashMap *hashMap)
{
    if (!hashMap || !(*hashMap)) return;

    HashMap map = *hashMap;

    map->clear(map);
    free(map);
    *hashMap = NULL;
}

HashMapIterator createHashMapIterator(HashMap hashMap)
{
    if (!hashMap) return NULL;

    HashMapIterator iterator = newHashMapIterator();
    if (!iterator) return NULL;

    iterator->hashMap = hashMap;
    iterator->count = 0;
    iterator->hashCode = -1;
    iterator->entry = NULL;
    return iterator;
}

Boolean hasNextHashMapIterator(HashMapIterator iterator)
{
    if (!iterator) return False;

    return (iterator->count < iterator->hashMap->size ? True : False);
}

HashMapIterator nextHashMapIterator(HashMapIterator iterator)
{
    if (!iterator) return NULL;

    if (hasNextHashMapIterator(iterator)) {
        // 冲突链表上还有节点, 就移动到链表节点的下一个位置
        if (iterator->entry != NULL && iterator->entry->next != NULL) {
            iterator->count++;
            iterator->entry = iterator->entry->next;
            return iterator;
        }
        // 冲突链表上没有数据，就移动到数组的下一个位置
        while (++iterator->hashCode < iterator->hashMap->listSize) {
            Entry entry = &iterator->hashMap->list[iterator->hashCode];
            if (entry->key != NULL) { // key非空，代表有数据
                iterator->count++;
                iterator->entry = entry;
                break;
            }
        }
    }

    return iterator;
}

void freeHashMapIterator(HashMapIterator *iterator)
{
    if (!iterator) return;

    if (*iterator != NULL) {
        free(*iterator);
    }

    *iterator = NULL;
}
